home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 21 / AACD 21.iso / AACD / Utilities / Ghostscript / src / shc.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-01  |  8.1 KB  |  259 lines
  1. /* Copyright (C) 1992, 1995, 1997, 1998 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of AFPL Ghostscript.
  4.   
  5.   AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author or
  6.   distributor accepts any responsibility for the consequences of using it, or
  7.   for whether it serves any particular purpose or works at all, unless he or
  8.   she says so in writing.  Refer to the Aladdin Free Public License (the
  9.   "License") for full details.
  10.   
  11.   Every copy of AFPL Ghostscript must include a copy of the License, normally
  12.   in a plain ASCII text file named PUBLIC.  The License grants you the right
  13.   to copy, modify and redistribute AFPL Ghostscript, but only under certain
  14.   conditions described in the License.  Among other things, the License
  15.   requires that the copyright notice and this notice be preserved on all
  16.   copies.
  17. */
  18.  
  19. /*$Id: shc.h,v 1.2 2000/09/19 19:00:50 lpd Exp $ */
  20. /* Common definitions for filters using Huffman coding */
  21.  
  22. #ifndef shc_INCLUDED
  23. #  define shc_INCLUDED
  24.  
  25. #include "gsbittab.h"
  26. #include "scommon.h"
  27.  
  28. /*
  29.  * These definitions are valid for code lengths up to 16 bits
  30.  * and non-negative decoded values up to 15 bits.
  31.  *
  32.  * We define 3 different representations of the code: encoding tables,
  33.  * decoding tables, and a definition table which can be generated easily
  34.  * from frequency information and which in turn can easily generate
  35.  * the encoding and decoding tables.
  36.  *
  37.  * The definition table has two parts: a list of the number of i-bit
  38.  * codes for each i >= 1, and the decoded values corresponding to
  39.  * the code values in increasing lexicographic order (which will also
  40.  * normally be decreasing code frequency).  Calling these two lists
  41.  * L[1..M] and V[0..N-1] respectively, we have the following invariants:
  42.  *      - 1 <= M <= max_hc_length, N >= 2.
  43.  *      - L[0] = 0.
  44.  *      - for i=1..M, L[i] >= 0.
  45.  *      - sum(i=1..M: L[i]) = N.
  46.  *      - sum(i=1..M: L[i] * 2^-i) = 1.
  47.  *      - V[0..N-1] are a permutation of the integers 0..N-1.
  48.  */
  49. #define max_hc_length 16
  50. typedef struct hc_definition_s {
  51.     ushort *counts;        /* [0..M] */
  52.     uint num_counts;        /* M */
  53.     ushort *values;        /* [0..N-1] */
  54.     uint num_values;        /* N */
  55. } hc_definition;
  56.  
  57. /* ------ Common state ------ */
  58.  
  59. /*
  60.  * Define the common stream state for Huffman-coded filters.
  61.  * Invariants when writing:
  62.  *      0 <= bits_left <= hc_bits_size;
  63.  *      Only the leftmost (hc_bits_size - bits_left) bits of bits
  64.  *        contain valid data.
  65.  */
  66. #define stream_hc_state_common\
  67.     stream_state_common;\
  68.         /* The client sets the following before initialization. */\
  69.     bool FirstBitLowOrder;\
  70.         /* The following are updated dynamically. */\
  71.     uint bits;        /* most recent bits of input or */\
  72.                 /* current bits of output */\
  73.     int bits_left        /* # of valid low bits (input) or */\
  74.                 /* unused low bits (output) in above, */\
  75.                 /* 0 <= bits_left <= 7 */
  76. typedef struct stream_hc_state_s {
  77.     stream_hc_state_common;
  78. } stream_hc_state;
  79.  
  80. #define hc_bits_size (arch_sizeof_int * 8)
  81. #define s_hce_init_inline(ss)\
  82.   ((ss)->bits = 0, (ss)->bits_left = hc_bits_size)
  83. #define s_hcd_init_inline(ss)\
  84.   ((ss)->bits = 0, (ss)->bits_left = 0)
  85.  
  86. /* ------ Encoding tables ------ */
  87.  
  88. /* Define the structure for the encoding tables. */
  89. typedef struct hce_code_s {
  90.     ushort code;
  91.     ushort code_length;
  92. } hce_code;
  93.  
  94. #define hce_entry(c, len) { c, len }
  95.  
  96. typedef struct hce_table_s {
  97.     uint count;
  98.     hce_code *codes;
  99. } hce_table;
  100.  
  101. #define hce_bits_available(n)\
  102.   (ss->bits_left >= (n) || wlimit - q > ((n) - ss->bits_left - 1) >> 3)
  103.  
  104. /* ------ Encoding utilities ------ */
  105.  
  106. /*
  107.  * Put a code on the output.  The client is responsible for ensuring
  108.  * that q does not exceed pw->limit.
  109.  */
  110.  
  111. #ifdef DEBUG
  112. #  define hc_print_value(code, clen)\
  113.     (gs_debug_c('W') ?\
  114.      (dlprintf2("[W]0x%x,%d\n", code, clen), 0) : 0)
  115. #  define hc_print_value_then(code, clen) hc_print_value(code, clen),
  116. #else
  117. #  define hc_print_value(code, clen) 0
  118. #  define hc_print_value_then(code, clen)    /* */
  119. #endif
  120. #define hc_print_code(rp) hc_print_value((rp)->code, (rp)->code_length)
  121.  
  122. /* Declare variables that hold the encoder state. */
  123. #define hce_declare_state\
  124.     register uint bits;\
  125.     register int bits_left
  126.  
  127. /* Load the state from the stream. */
  128. /* Free variables: ss, bits, bits_left. */
  129. #define hce_load_state()\
  130.     bits = ss->bits, bits_left = ss->bits_left
  131.  
  132. /* Store the state back in the stream. */
  133. /* Free variables: ss, bits, bits_left. */
  134. #define hce_store_state()\
  135.     ss->bits = bits, ss->bits_left = bits_left
  136.  
  137. /* Put a code on the stream. */
  138. void hc_put_code_proc(P3(bool, byte *, uint));
  139.  
  140. #define hc_put_value(ss, q, code, clen)\
  141.   (hc_print_value_then(code, clen)\
  142.    ((bits_left -= (clen)) >= 0 ?\
  143.     (bits += (code) << bits_left) :\
  144.     (hc_put_code_proc((ss)->FirstBitLowOrder,\
  145.               q += hc_bits_size >> 3,\
  146.               (bits + ((code) >> -bits_left))),\
  147.      bits = (code) << (bits_left += hc_bits_size))))
  148. #define hc_put_code(ss, q, cp)\
  149.   hc_put_value(ss, q, (cp)->code, (cp)->code_length)
  150.  
  151. /*
  152.  * Force out the final bits to the output.
  153.  * Note that this does a store_state, but not a load_state.
  154.  */
  155. byte *hc_put_last_bits_proc(P4(stream_hc_state *, byte *, uint, int));
  156.  
  157. #define hc_put_last_bits(ss, q)\
  158.   hc_put_last_bits_proc(ss, q, bits, bits_left)
  159.  
  160. /* ------ Decoding tables ------ */
  161.  
  162. /*
  163.  * Define the structure for the decoding tables.
  164.  * First-level nodes are either leaves, which have
  165.  *      value = decoded value
  166.  *      code_length <= initial_bits
  167.  * or non-leaves, which have
  168.  *      value = the index of a sub-table
  169.  *      code_length = initial_bits + the number of additional dispatch bits
  170.  * Second-level nodes are always leaves, with
  171.  *      code_length = the actual number of bits in the code - initial_bits.
  172.  */
  173.  
  174. typedef struct hcd_code_s {
  175.     short value;
  176.     ushort code_length;
  177. } hcd_code;
  178.  
  179. typedef struct hcd_table_s {
  180.     uint count;
  181.     uint initial_bits;
  182.     hcd_code *codes;
  183. } hcd_table;
  184.  
  185. /* Declare variables that hold the decoder state. */
  186. #define hcd_declare_state\
  187.     register const byte *p;\
  188.     const byte *rlimit;\
  189.     uint bits;\
  190.     int bits_left
  191.  
  192. /* Load the state from the stream. */
  193. /* Free variables: pr, ss, p, rlimit, bits, bits_left. */
  194. #define hcd_load_state()\
  195.     p = pr->ptr,\
  196.     rlimit = pr->limit,\
  197.     bits = ss->bits,\
  198.     bits_left = ss->bits_left
  199.  
  200. /* Store the state back in the stream. */
  201. /* Put back any complete bytes into the input buffer. */
  202. /* Free variables: pr, ss, p, bits, bits_left. */
  203. #define hcd_store_state()\
  204.     pr->ptr = p -= (bits_left >> 3),\
  205.     ss->bits = bits >>= (bits_left & ~7),\
  206.     ss->bits_left = bits_left &= 7
  207.  
  208. /* Macros to get blocks of bits from the input stream. */
  209. /* Invariants: 0 <= bits_left <= bits_size; */
  210. /* bits [bits_left-1..0] contain valid data. */
  211.  
  212. #define hcd_bits_available(n)\
  213.   (bits_left >= (n) || rlimit - p > ((n) - bits_left - 1) >> 3)
  214. /* For hcd_ensure_bits, n must not be greater than 8. */
  215. #define HCD_ENSURE_BITS_ELSE(n)\
  216.   if (bits_left >= n)\
  217.     DO_NOTHING;\
  218.   else HCD_MORE_BITS_ELSE
  219. #define hcd_ensure_bits(n, outl)\
  220.   BEGIN HCD_ENSURE_BITS_ELSE(n) goto outl; END
  221.  
  222. /* Load more bits into the buffer. */
  223. #define HCD_MORE_BITS_1_ELSE\
  224.   if (p < rlimit) {\
  225.     int c = *++p;\
  226. \
  227.     if (ss->FirstBitLowOrder)\
  228.       c = byte_reverse_bits[c];\
  229.     bits = (bits << 8) + c, bits_left += 8;\
  230.   } else
  231. #if hc_bits_size == 16
  232. #  define HCD_MORE_BITS_ELSE HCD_MORE_BITS_1_ELSE
  233. #else /* hc_bits_size >= 32 */
  234. #  define HCD_MORE_BITS_ELSE\
  235.   if (rlimit - p >= 3) {\
  236.     if (ss->FirstBitLowOrder)\
  237.       bits = (bits << 24) + ((uint)byte_reverse_bits[p[1]] << 16) + ((uint)byte_reverse_bits[p[2]] << 8) + byte_reverse_bits[p[3]];\
  238.     else\
  239.       bits = (bits << 24) + ((uint)p[1] << 16) + ((uint)p[2] << 8) + p[3];\
  240.     bits_left += 24, p += 3;\
  241.   } else HCD_MORE_BITS_1_ELSE
  242. #endif
  243. #define hcd_more_bits(outl)\
  244.   BEGIN HCD_MORE_BITS_ELSE goto outl; END
  245.  
  246. #define hcd_peek_bits(n) ((bits >> (bits_left - (n))) & ((1 << (n)) - 1))
  247.  
  248. /* hcd_peek_var_bits requires bits_left <= 8. */
  249. #define hcd_peek_var_bits(n)\
  250.   ((bits >> (bits_left - (n))) & byte_right_mask[n])
  251.  
  252. /* hcd_peek_bits_left requires bits_left <= 8. */
  253. #define hcd_peek_bits_left()\
  254.   (bits & byte_right_mask[bits_left])
  255.  
  256. #define hcd_skip_bits(n) (bits_left -= (n))
  257.  
  258. #endif /* shc_INCLUDED */
  259.